1. Field of The Invention
This invention is related to a first-in-first-out (FIFO) memory system and in particular to a high speed FIFO memory having a plurality of "fall-through" stacks.
2. Description of The Prior Art
FIG. 1 shows the block diagram of a FIFO memory system which is drawn broadly enough to encompass prior art FIFO memories as well as the FIFO memory system of the present invention.
This generic FIFO memory buffer 10 includes a FIFO memory 4 which allows the simultaneous writing of data through its input port 1 and the reading out of data through its output port 7, respectively. In addition a first-in-first-out protocol is imposed upon the data which is first written into and then read out of the memory.
Input control logic 2 provides information to the user describing whether the FIFO memory 4 is filled to capacity and also provides information to the user describing whether the FIFO memory is ready to receive additional data. Output control logic 5 provides information to the user describing whether the memory is empty and whether data is available to be read out of the memory. When the FIFO memory 4 is filled to capacity, the input control logic 2 prohibits additional data input to the FIFO memory 4. Similarly, when the FIFO memory 4 is empty, the output control logic 5 prohibits attempted removal of data from the FIFO memory 4.
The data input buffer 3 electrically buffers the input signals which appear at input port 1 and generates the voltage levels of the data input signals required by the FIFO memory 4 for proper operation.
The data output buffer 6 electrically buffers the signals representing a data word read-out of the FIFO memory 4 and presents the buffered signals to external circuitry (not shown).
The feature which distinguishes a FIFO memory system 10 from a standard shift register is the ability, when proper internal operating conditions are met, to operate the input and output ports completely asynchronously, including the reading and writing of data at different speeds.
Prior art FIFO memory systems can be divided into two classes which depend on their internal organization: fall-through systems and pointer-based systems.
The internal organization of a fall-through FIFO memory system 19 is depicted in FIG. 2. The fall-through FIFO memory 20 includes a stack 21 of data registers, numbered consecutively 21-0 to 21-(N-1), a stack 23 of control registers 23-0, . . ., 23-(N-1), and word propagation logic 27.
The operation of this system is analogous to that of a bucket brigade. Each control register 23-0 through 23-(N-1) associated with data registers 21-0 through 21-(N-1), respectively, contains a logical zero if its associated data register is empty and stores a logical one if its associated data register contains information. Consider first the case of an empty memory. For an empty memory, control registers 23-0 through 23-(N-1) will each store a logical zero. When a data word is shifted into fall-through FIFO memory 20 from the input port 28, it is latched into data register 21-0, and control register 23-0 is set to a logical one. When this shifting-in cycle is complete, word propagation logic 27 detects the condition that control register 23-1 stores a logical zero (i.e., that data register 21-1 is empty) and that control register 23-0 stores a logical one (i.e., that data register 21-0 is full), initiates a transfer of data from data register 21-0 to data register 21-1 and resets control register 23-0 to a logical zero so that it indicates that data register 21-0 is empty and sets control register 23-1 to logical one so that it indicates that data register 21-1 is full. In like fashion, the data word will be transferred through each data register of the fall-through FIFO memory consecutively until it reaches data register 21-(N-1). The next word written into the mcmory will fall-through to data register 21-(N-2); in this fashion, data words will continue to fall-through and stop in data registers consecutively closer to the data input buffer 22 until the fall-through FIFO memory 20 is full. A word may be shifted into data register 21-0 whenever control register 23-0 stores a logical zero; and each word in the memory falls from a given data register to the next lower data register in the stack when the word propagation logic 27 detects that the given control register stores a logical one and the next lower control register stores a logical zero, so that more than one word may be in the fall-through process at a given time. When a data word is shifted out of the memory, the shifting out procedure resets control register 23-(N-1) from a logical one to a logical zero. In the typical fall-through fashion, if control register 23-(N-2) contains a logical one the data word in data register 21-(N-2) will propagate forward to data register 21-(N-1) and appear at the output port 29. All remaining words in the FIFO will successively advance one data register toward the data output buffer 24. Data input is permitted by the input control logic 25 if and only if control register 23-0 at the top of stack 23 contains a logical zero, indicating that data register 21-0 is empty. Similarly, data output is permitted by the output control logic 26 if and only if control register 23-(N-1) at the bottom of stack 23 contains a logical one, indicating that data register 21-(N-1) is full.
One example of a prior art fall-through memory system is contained in U.S. Pat. No. 4,151,609 entitled "FIRST IN FIRST OUT (FIFO) MEMORY", issued to Moss in 1979, which is assigned to Monolithic Memories, Inc., the assignee of this application, and which is incorporated herein by reference.
There are three features of the operation of a fall-through FIFO memory system which are particularly important for comparison with the operation of a pointer-based FIFO memory system. First, there is a significant delay (fall-through time) associated with the propagation of the first word entered into data register 21-0 of an empty fall-through FIFO memory to the last data register 21-(N-1). This delay also exists for the backward propagation of an empty register position from the output data register position (data register 21-(N-1)) back to the input register position (data register 21-0) when a data word is shifted out of a full fall-through FIFO memory. This delay is a direct result of the fact that each data word must pass through every register in the fall-through FIFO memory before it is read out.
Second, there is a serious limitation on shift-in (and shift-out) cycle time that is imposed by the "fall-through" architecture: that is, the theoretical maximum data transfer rate at either the input port 28 or the output port 29 is only 50% of the apparent shifting frequency of the fall-through register stack. The precise reasoning behind this limit is intricate, but can be summarized by noting that the shifting of data into data register 21-0 of two consecutive data words at high speeds requires the following sequence of operations:
1. The first data word is shifted into data register 21-0 of the fall-through stack 21 from the input port 28 via data input buffer 22. PA1 2. The first data word is shifted from the data register 21-0 to the data register 21-1. PA1 3. The second data word is shifted from the data input port into the data register 21-0 as soon as but not prior to the completion of the shift operation described above in step number 2.
The third important feature of fall-through FIFO organization is the constraint that data always moves from the data input port 28 into the same physical memory location, passes through the same sequence of physical memory positions, and moves from the same physical memory location through the data output buffer 24 to the output port 29.
The internal organization of a pointer-based FIFO memory system is depicted in FIG. 3. The pointer-based FIFO memory 30 comprises a random access memory (RAM) 31, which is used for data storage, and control logic 32. Control logic 32 creates the FIFO protocols and controls the interface between the input port 35 and the RAM 31 and also controls the interface between the RAM 31 and the output port 36.
The control logic 32 includes two counters, input address counter 32-1 and output address counter 32-2, an address magnitude comparator 32-3, and miscellaneous control logic 32-4. Input address counter 32-1 generates the address of the storage location where the next data input word is to be stored and output address counter 32-2 generates the address of the storage location from which the next data output word is to be taken. Address magnitude comparator 32-3 compares the two counter addresses currently stored in the input and output address counters 31-1 and 32-2 and identifies if RAM 31 is either full or empty, respectively. Miscellaneous control logic 32-4 generates the internal RAM control signals and provides signals to the input control logic 33 and to the output control logic 37 which indicate the status of the RAM 31 and the control logic 32.
For descriptive purposes the addresses generated by the input and output address counters may be denominated 0, 1, 2, . . . N-1, where N is the number of storage locations in the RAM 31 available for storing data words. Each address corresponds to a unique word storage location in the RAM 31.
The operation of the pointer based FIFO memory 30 is straightforward. When initialized the FIFO RAM 31 is empty and both the input and output address counters 32-1 and 32-2, respectively "point" to address 0. (A counter is said to "point" to the address k if k is the number in the counter.) When the first word W(0) is loaded into the FIFO RAM 31 from input port 35 via data input buffer 34, it is loaded into RAM 31 at the word storage location having address 0.
In general, the input address counter 32-1 points to the storage location whose address is k (mod N) where k is the number of data words previously stored (k=0,1,2, . . .), and k (mod N) is the integral remainder when k is divided by N. In other words, the input data words W(0), W(1), . . . , W(k), . . . are stored cyclically in the RAM 31, with data word W(k) being stored in the storage location whose address is k (mod N) for k=0, 1, . . . . The comparator 32-3 senses when the input address counter points to an address whose storage location is full and then data entry is prohibited by the control logic 32.
In general, the output address counter 32-2 points to the storage location whose address is j (mod N) where j is the number of data words previously read out of the RAM, where j=0,1,2, . . . . Thus, the data output words are also read out cyclically. Again readout is prohibited by the control logic 32 when the comparator 32-3 senses that the output address counter points to an address whose storage location is empty.
In view of the above formulas it is easy to see that the addresses on the input and output counters are equal if and only if the FIFO RAM 31 is either empty or full. For if the addresses are equal, then k.tbd.j (mod N). Under the constraints imposed above, either k=j in which case the number of data words previously stored equals the number of data words previously read out, i.e., the RAM is empty, or k=(j+N), in which case the number of data words previously stored exceeds the number of data words previously read out by N, the number of word storage locations in the RAM 31, i.e., the RAM 31 is full.
Conversely, if RAM 31 is empty, the number of data words previously stored equals the number of words previously read out, i.e. k=j so k.tbd.j (mod N); and if RAM 31 is full, the number of data words previously stored exceeds the number of data words previously read out by N, i.e., k=(j+N), so again k.tbd.j (mod N). Thus if RAM 31 is empty or full, the addresses k (mod N) and j (mod N) in input address counter 32-1 and output address counter 32-2, respectively, are equal.
The magnitude comparator identifies whether the RAM is empty or full by determining whether k.tbd.j(mod N), and signals the miscellaneous control logic to either allow or prohibit data entry at the input port 35 or allow or prohibit data removal at the output port 36.
One description of a prior art pointer based FIFO memory system is contained in Column 1, lines 47-68 and Column 2, lines 1-58 of U.S. Pat. No. 4,374,428 entitled "EXPANDABLE FIFO SYSTEM", issued to Barnes, Feb. 15, 1983, which is hereby incorporated by reference.
Barnes improves upon this prior art system by providing an expandable number N of individual FIFO devices arranged to form a ring of identical FIFO devices connected in an identical manner where each device comprises a memory having N storage locations and pointing means which directs the writing of words into successive storage locations until read out of the FIFO system.
There are significant differences between the operation of a pointer-based FIFO memory system and a fall-through FIFO memory system. First, there is no fall-through time associated with a pointer-based memory that is akin to that of a fall-through type. There is a delay from data input to available data output, but it is short, caused by a small number of gate delays and not related to the fall-through phenomenon.
Second, the limitation on shift-in and shift-out cycle time in a pointer-based FIFO memory is imposed by a different sequence of events than in a fall-through FIFO memory. With each data shift operation, the pertinent counter must increment, the magnitude comparator must settle, i.e., determine whether or not a full or empty state exists, and the port control signals must be adjusted before the next shift operation can occur. The cycle time increases with the total word size of a pointer-based FIFO memory because larger FIFO memories require longer word addresses and hence longer delays for the settling of the magnitude comparator.
Lastly, in a pointer-based FIFO memory it is apparent that data can be input or output from any physical location in the data memory, due to the fact that a RAM structure is used as the core of the device.